# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

from heapq import heapify, heappop
class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        # 读取所有节点值
        h = []
        for node in lists:
            while node:
                h.append(node.val)
                node = node.next
        # 构造一个最小堆
        if not h:
            return None
        heapify(h)  # 转换成最小堆

        # 构造链表
        root = ListNode(heappop(h))
        curnode = root
        while h:
            nextnode = ListNode(heappop(h))
            curnode.next = nextnode
            curnode = nextnode
        return root
